package com.cty.B_SpecialDataStructures.B_Queue.QueueArray;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/14 7:48
 * @Description: 数组实现队列
 * 应用场景：
 *      数据量可预测或内存充足时使用
 * 重要操作：
 *      ① peek(): DataItem    O(1)
 *      ② insert(DataItem): boolean    O(1)
 *      ③ remove(): DataItem    O(1)
 * @version: 1.0
 */
public class QueueArray {
    private int maxSize;
    private DataItem[] array;
    private int nItems;
    private int front;
    private int rear;

    public QueueArray(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
        front = 0;
        rear = -1;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayQueue(){
        if(isEmpty())
            return;

        if(rear >= front) {  // 未循环
            for(int i=front; i<=rear; i++)
                System.out.print(array[i].getKey() + " ");  // front --> rear
        }else{
            for(int i=front; i<maxSize; i++)
                System.out.print(array[i].getKey() + " ");  // front -- > maxSize-1
            for(int i=0; i<=rear; i++)
                System.out.print(array[i].getKey() + " ");  // 0 -- > rear
        }
        System.out.println();
    }  // end displayQueue()

    /**
     * 查看队头  O(1)
     * @return
     */
    public DataItem peek(){
        if(isEmpty())
            return null;

        return array[front];
    }  // end peek()

    /**
     * 在队尾插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        rear = (rear + 1) % maxSize;  // 当rear==maxSize时，令rear=0
        array[rear] = item;

        nItems++;
        return true;
    }  // end insert()

    /**
     * 在队头删除数据  O(1)
     * @return
     */
    public DataItem remove(){
        if(isEmpty())
            return null;

        DataItem temp = array[front];
        front = (front + 1) % maxSize;  // 当front==maxSize时，令front=0
        nItems--;
        return temp;
    }  // end remove()

}  // end QueueArray{}
